README.md

109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 

Solutions (Python)

1. Convert to Array

# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = None# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution: defsortedListToBST(self, head: ListNode) ->TreeNode: defsortedArrayToBST(nums: List[int]) ->TreeNode: ifnotnums: returnNonemid=len(nums) //2root=TreeNode(nums[mid]) root.left=sortedArrayToBST(nums[:mid]) root.right=sortedArrayToBST(nums[mid+1:]) returnrootnums= [] whilehead: nums.append(head.val) head=head.nextreturnsortedArrayToBST(nums)